An error correction and detection system used in communication systems detects errors due to noise or other signal impairments during transmission to enable error localization and error correction. Forward error correction (FEC) permits error control for data transmission, and differs from standard error detection and correction systems because the receiver can correct errors without requesting a retransmission of data. The design of the code used in any FEC system determines the maximum fraction of errors that can be corrected in advance. As a result, different FEC codes can be suitable for different conditions.
For example, in many FEC schemes, redundancy is added to transmitted data using a predetermined algorithm. Each of the redundant bits is a complex function of the original information bits. As a result, the encoded output may or may not include the original information. Unmodified inputs at the output are systematic codes and those that are not are non-systematic.
FEC schemes could be considered to average the noise because each data bit affects many transmitted symbols. Some symbols are corrupted more by noise than others and this allows the original data to be extracted from the other, less corrupted received signals that depend on the same user data. As FEC codes approach the theoretical Shannon limit and stronger codes are used, an FEC scheme works well above a minimum signal-to-noise ratio, but typically fails when the signal is below that minimum ratio.
For higher modem data rates, for example, greater than 1 Mbps, the computational complexity of FEC schemes can be prohibitive given the current state of commercially available digital signal processors (DSPs) and Field Programmable Gate Array (FPGA) technology.
The use of Forward Error Correction (FEC) and the Maximum Likelihood Decoder (e.g. Viterbi Algorithm) are described exhaustively in most standard communications texts including “Digital Communications” by John G. Proakis. Continuous Phase Modulation is described in detail in books such as “Digital Phase Modulation” by Anderson, Aulin and Sundberg and “Digital Communications” by John G. Proakis.
In digital communications systems, for example, cellular and PCS (personal communications systems), computer communications systems, and SATCOM (satellite communications) systems, digital data is modulated by the modem onto a signal to be transmitted over a communications channel. Data is typically encoded before transmission to a receiver or to a storage device, to protect the data from errors, which may result from a noisy communications channel or a defect in the storage medium. An encoder manipulates data symbols in accordance with an error correction code and produces error correction symbols or a structured redundancy output sequence. When the code word is later received or retrieved it is decoded to reproduce the data symbols, and errors in the data symbols are corrected, if possible, using the error correction symbols or the structured redundancy of code.
For the following discussion, a convolutional codeword is defined as the n output bits that are generated based on an input of k input bits (i.e., rate k/n code). One method of decoding code words encoded using a convolutional code is maximum likelihood decoding. One kind of maximum likelihood decoder is commonly referred to as a Viterbi decoder. Conceptually, a Viterbi decoder uses a decoding trellis, which has a branch for each possible code word and connected paths of branches for each possible stream, or sequence, of code words. The decoder essentially finds a path through the trellis, which is “closest” to, or most like, the received stream of code words. It then treats the code words on this “most likely” trellis path as the received code words and assigns data values to them, to produce a best estimate of the transmitted data.
To determine the most likely path, the decoder calculates, for each received code word, a set of branch metrics as numerical representation of the likelihood that the transmitted code word, which may contain errors on reception, is actually the code word which corresponds to a particular branch. In one such decoder the branch metrics are the Hamming distances between the received code word and the code words associated with the various branches.
Each branch in the decoding trellis leads from an initial state, which represents the state that the registers are in prior to the formulation of the code word associated with the branch, and leads to an end state, which represents the state that the registers are in after the formulation of the code word. For a binary code there are 2K−1 possible states associated with each decoding level, where K is the constraint length of the code. For example, the code may have a constraint length of 3, i.e., there are 2 registers, and there are thus 4 possible register states, namely, 00, 01, 10, 11, in each decoding level. Since the code is a rate 1/n code, i.e. binary code so k=1, there are two possible branches leading from each initial state, namely a branch associated with a zero data bit and a branch associated with a one data bit. Each of these branches necessarily leads to a different end state. Thus, for each of the 2K−1 states in a given decoding stage, there are two branches leading to each of these states, and each branch may represent the transmitted code word. Accordingly, to decode the code word the decoder must determine two branch metrics for each of the 2K−1 possible end states, or a total of 2(2K−1) branch metrics. For convolutional codes, there are only 2n unique branch metric values.
Once the decoder calculates these branch metrics, it next determines the metrics of the various paths leading to the end states. Accordingly, the decoder adds to the branch metrics the appropriate path metrics, which are the sums of the branches leading to the current starting states. The decoder then selects a most likely path leading to each of the end states and stores for later use the path metrics and information, which identifies these most likely paths. These most likely paths, which are also referred to as the “surviving paths.” The decoder does not retain information relating to the less likely, or non-surviving, paths. In this way, the decoder “prunes” these paths from the trellis, and thereby eliminates for a next level of decoding a portion of the path metric calculations.
When a sufficient number of code words have been included in the trellis paths, the most likely code word path is chosen from the surviving paths associated with the end states. The decoder selects as the most likely path the code word path which is “closest” to the received data, i.e., the path with the smallest Hamming distance metric. The decoder then decodes the code words on the most likely path, or “traces back” along the path, to determine the associated data bits.
The Viterbi algorithm is used not only to decode convolutional codes but also to produce the maximum-likelihood estimate of the transmitted sequence through a channel with intersymbol interference (ISI), and to decode trellis-coded modulation (TCM) and other modulations with memory. The Viterbi decoder is typically divided into three functional parts. The first part is an add-compare-select (ACS) unit that is used to calculate the path metrics. The second part is the survivor memory control unit for survivor memory management, which may store the survivor sequences as last part of the Viterbi decoder.
Continuous phase modulation (CPM) is being applied in communications due to its bandwidth efficiency and constant envelope characteristics. With CPM, the modulated signal phase transitions are smoothed. For example, with Binary Phase-Shift Keying (BPSK), a logic one is transmitted as one phase of a modulated signal, and a logic zero is transmitted as 180-degree phase-shifted with a sharp transition (i.e., instantaneous) in phase. This sharp phase transition results in broadening of the transmitted spectrum. With CPM the phase of the transmitted signal makes smooth phase changes over the bits of the modulating digital signal. An example of CPM is Minimum Shift Keying (MSK) modulation.
Multi-h continuous phase modulation (multi-h CPM) is itself a broad class of modulated waveforms. The class includes signals with constant amplitude but varying phase. Multi-h CPM differs from the single-h format by using a set of H modulation indices in a cyclic manner. This results in the delayed merging of neighboring phase trellis paths and ultimately, in improved error performance. A detailed description of multi-h CPM waveforms is included in the book “Digital Phase Modulation” by Anderson, Aulin, and Sundberg, Plenum Press, New York, 1986.
As described by articles in Svensson, “Reduced State Sequence Detection of Full Response Continuous Phase Modulation,” Electronics Letter, May 10, 1990, Vol. 26, No. 10; and Eyuboglu et al., “Reduced State Sequence Estimation With Set Partitioning and Decision Feedback,” IEEE Transactions on Communications, January 1988, Vol. 36, No. 1, (and others), some techniques reduce the complexity of the standard MLSE (Maximum Likelihood Sequence Estimator) decoders. For example, in Eyuboglu, a reduced-state sequence estimator for linear intersymbol interference (ISI) channels uses a conventional Viterbi algorithm (VI) with decision feedback to search in a reduced-state “subset trellis” which is constructed using set partitioning principles. The complexity of maximum likelihood sequence estimation (MLSE) due to the length of the channel memory and the size of the signal set is systematically reduced. An error probability analysis shows that a good performance/complexity tradeoff can be obtained. In Svensson, a reduced state sequence detector (RSSD) combines decision feedback with Viterbi decoding for M-ary full response continuous phase modulation. The detector is analyzed with minimum Euclidean distances and by simulations of the symbol error probability. The M-ary full response CPM schemes can be decoded by a decoder with only two states, when the modulation index is relatively small (<1/M) and for larger modulation indexes less than one with M states. There are several variants of the reduced state MLSE decoders, which do not provide the same (reduced) complexity or modem bit error rate performance.
The use of Forward Error Correction (FEC) and the maximum likelihood decoder (Viterbi algorithm) is described in most standard communications texts. Reduced state sequence estimation (RSSE) was an important development in MLSE decoder design in the 1980's. The developers and manufacturers XILINX and Altera produce FPGA and VHSIC Hardware Description Language (VHDL) tools that allow users a few programmable Viterbi (NLSE) options. These are usually formed as convolutional codes with the ability to provide soft decision metrics. None of the current tools provide for a desired decision feedback or trellis structure manipulation required for reduced-state sequence estimation. They also are not programmable for use with CPM signals and signals with memory. Also, there exists a need in the industry for a reduced state, generic, programmable maximum likelihood decoder.